Computability and Complexity of Unconventional Computing Devices

摘要

We discuss some claims that certain UCOMP devices can performhypercomputation (compute Turing-uncomputable functions) or performsuper-Turing computation (solve NP-complete problems in polynomial time). Wediscover that all these claims rely on the provision of one or more unphysicalresources.